
def kmp_match(s, p): # p in s
    m = len(s); n = len(p)
    cur = 0#起始指针cur
    table = partial_table(p)
    while cur<=m-n:
        for i in range(n):
            if s[i+cur]!=p[i]:
                cur += max(i - table[i-1], 1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
                break
        else:
            return True 
    return False #可返回0

#部分匹配表
def partial_table(p):
    # '''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
    prefix = set()
    postfix = set()
    ret = [0]
    for i in range(1,len(p)):
        prefix.add(p[:i])
        postfix = {p[j:i+1] for j in range(1,i+1)}
        ret.append(len((prefix&postfix or {''}).pop()))
    return ret

#朴素匹配（单一字符）
def naive_match(s, p): # p in s
    true = 0; lenth = 0; kkk = False 
    m = len(s)
    for i in range(m):#起始指针i
        if lenth == 0:
            kkk = True
        if s[ i : i + 1 ] == p[ lenth : lenth + 1 ] and kkk:
            true = lenth + 1
            lenth += 1
        else:
            kkk = False
            lenth = 0
    return true #返回匹配的最大长度


# --------------------- 
# 作者：mattkang 
# 来源：CSDN 
# 原文：https://blog.csdn.net/handsomekang/article/details/40978213 
# 版权声明：本文为博主原创文章，转载请附上博文链接！


# sss = '123rtyuiohjgasd'
# ppp = 'rtyhj'
# true = naive_match(sss,ppp)
# print(true)